A Ternary Content Addressable Memory (“TCAM”) is a type of computer memory used in certain high speed searching applications, such as routing information through a network. It is designed such that it receives a data word and searches its entire memory to see if that data word is stored anywhere in it. If the data word is found, the TCAM returns a list of one or more storage addresses where the word was found. The data word may consist of 1s, 0s, and Xs (“wildcard” bits). For example, a TCAM might have a stored word of “10XXO” which will match any of the four search words “10000,” “10010,” “10100,” or “10110.”
TCAMs, which take up a lot of power and space, are a versatile but highly constrained resource to support flexible packet processing actions on network switching devices. Next generation network applications, such as Openflow network fabrics, large firewalls, or policy-based routing, require very large sets of flow rules to enable them effectively. The small TCAMs on many devices limit the scalability of many of these applications. Therefore, it is desirous to minimize rule sets stored in TCAMs to enable network applications to operate effectively.
Attempts to minimize TCAM rule sets have been made, but these attempts are very limited. For example, one rule minimization technique supports only two known actions, as opposed to any number of arbitrary actions, which severely limits its application in network switching. Another known technology is the hardware Layer 3 IP prefix table in L3 switching devices. However, these tables only perform longest prefix match of the destination IP address and cannot handle generic flow matches as required by next-generation network applications.